/**
 * @Author Fizz Pu
 * @Date 2020/8/27 下午9:21
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.Arrays;

/**
 *
 * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
 *
 * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
 *
 * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Lee1011 {
    // 这个题和koko吃香蕉很像
    // 都是先用for循环暴力猜出方程的解，最后利用二分搜索优化
    // 细节想清楚

    public int shipWithinDays(int[] weights, int D) {
        int minWight = Integer.MIN_VALUE, sums = 0;
        for (int weight : weights){
            minWight = Math.max(minWight, weight);
            sums += weight;
        }
        /*for(int i = minWight; i < Integer.MAX_VALUE; ++i){
            if(isTransportUp(i, D, weights))return i;
        }*/

        // 二分法
        int left = minWight, right = sums + 1, mid;
        while (left < right){
            mid = left + (right - left)/2;
            if(isTransportUp(mid, D, weights)){
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     *
     * @param maxWeight 最大运输量
     * @return D天能够运输完成返回true,否则返回false
     */


    //这个函数是核心
    boolean isTransportUp(int maxWeight, int D, int[] weights){
        // 遍历数组
        int day = 0, i;
        int sums = 0;
        for(i = 0 ;i < weights.length; ++i){
            sums += weights[i];
            if (sums > maxWeight){
                ++day;
                sums = weights[i]; // 秒啊！
                // i = i - 1; 下轮循环时本次循环继续，这回死循环的
            }
        }
        // 忽略了边界检查,至少要day+1天
        return  day + 1 <= D;
    }

    public static void main(String[] args) {
        Lee1011 lee1011 = new Lee1011();
        // System.out.println(lee1011.isTransportUp(15, 5, new int[]{1,2,3,4,5,6,7,8,9,10}));
        System.out.println(lee1011.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5));
        System.out.println(lee1011.shipWithinDays(new int[]{1,2,3,1,1}, 4));
    }

}
